package leet;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author fance
 * @date 18-4-19 下午1:05
 */
public class Solution {

    // arr must be sorted.
    public int binarySearch(int[] arr, int target) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (target == arr[mid]) {
                return mid;
            } else if (target > arr[mid]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public int mySqrt(int x) {
        // 1.return (int) Math.sqrt(x);

        if (x <= 1) {
            return x;
        }
        int lo = 1;
        int hi = x;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int sqrt = x / mid;
            if (sqrt == mid) {
                return mid;
            } else if (sqrt < mid) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return hi;
    }

    public int arrangeCoins(int n) {
        int level = 0;
        while (n > 0) {
            level++;
            n -= level;
        }
        return n == 0 ? level : level - 1;
    }

    public int singleNonDoubleInSortedArray(int[] arr) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid % 2 != 0) {
                mid--;
            }
            if (arr[mid] == arr[mid + 1]) {
                lo = mid + 2;
            } else {
                hi = mid;
            }
        }
        return arr[lo];
    }

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0;
        int j = 0;
        while (i < g.length && j < s.length) {
            if (g[i] < s[j]) {
                i++;
            }
            j++;
        }
        return i;
    }


    /**
     * 461. 汉明距离
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

    /**
     *
     * @param moves
     * @return
     */
    public boolean judgeCircle(String moves) {
        if (moves == null || moves.length() < 1) {
            return false;
        }
        int x = 0;
        int y = 0;
        for (int i = 0; i < moves.length(); i++) {
            char cur = moves.charAt(i);
            switch (cur) {
                case 'L' : x--; break;
                case 'R' : x++; break;
                case 'U' : y++; break;
                case 'D' : y--;
            }
        }
        return x == 0 && y == 0;
    }
    @Test
    public void test() {
        System.out.println(judgeCircle("UD"));

        /*int[] arr = {1,1,2,2,3,3,4};
        System.out.println(singleNonDoubleInSortedArray(arr));
   */
    }
}
